#!/usr/bin/env python
# encoding: utf-8
'''
@author: Excelsiorly
@license: (C) Copyright 2022, All Rights Reserved.
@contact: excelsiorly@qq.com
@file: 039. 组合总和.py
@time: 2022/1/21 13:22
@desc: https://leetcode-cn.com/problems/combination-sum/
> 给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。 
对于给定的输入，保证和为 target 的不同组合数少于 150 个。

@解题思路：
    1. 回溯
    2. Ot(S), Os(target)
'''


class Solution(object):
    def combinationSum(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        candidates.sort()

        def backtrack(candidates, target, path):
            if target == 0:
                res.append(path)
            if target < 0:
                return
            n = len(candidates)
            for i in range(n):
                # 因为已经排序过了，所以如果大了，后面元素也不用看了
                if candidates[i] > target: break
                # 否则就加入这个元素，继续递归
                backtrack(candidates[i:], target - candidates[i], path + [candidates[i]])

        res = []
        backtrack(candidates, target, [])
        return res